/*
作者：郝伟老师
简介：本文模拟了一个100人选择飞机座位的问题。
参考：https://blog.csdn.net/weixin_43145361/article/details/114365085
编译：javac -encoding UTF-8 .\SeatAllocation.java; java SeatAllocation 1000000
注意：
1. （坑）最后一个人不是第size()-1个人，因为乘客是随机上的，如果搞错结果不为50%

【更新历史】
2024/02/21 新建此类

*/
import java.util.*;

public class SeatAllocation{

    public static void main(String[] args){
        // 三个变量分别为总测试次数，座位数和命中次数。
        int total_tests = args.length > 0 ? Integer.parseInt(args[0]) : 100;
        int seat_count = args.length > 1 ? Integer.parseInt(args[1]) : 100;
        int hit_count = 0; 

        // 进行指定数量的测试并累计结果
        for(int i = 0; i < total_tests; i ++) 
                hit_count += OneTest(seat_count, total_tests * seat_count <= 1000);

        // 输出结果
        System.out.printf("hit count: %d, total tests: %d, hit rate: %.2f%%.\n", 
                                  hit_count, total_tests, hit_count*100.0/total_tests);
    }

    // 用于产生随机值的静态变量
    public static Random random = new Random();

    // 模拟一次实验过程，返回最后一位乘客否座位为自己的，是返回1,否则返回0
    public static int OneTest(int seat_cont, boolean display){
        // 可用的座位共seat_cont个，编号范围[0, seat_cont-1]
        var available_seats = new ArrayList<Integer>();
        var tickets = new ArrayList<Integer>();
        var arrangement = new HashMap<Integer, Integer>();
        for(int i = 0; i < seat_cont; i++){
            tickets.add(i);
            available_seats.add(i);
        }
        // 洗牌，因为人员登机也是随机的。
        Collections.shuffle(tickets);

        if(display){
            System.out.println("**********************************************");
            System.out.println(listToString(tickets));
        }

        // 建立了一张哈希表，记录乘客的票号和实际座位号，格式为：
        // [(票号, 座位号), (票号, 座位号), ...]

        for(int i = 0; i < seat_cont; i++){
            int ticket_no = tickets.get(i);
            int seat_no = ticket_no;
            // 第1个人随机坐或没有位置的人都随机坐。
            if(i == 0 || !available_seats.contains(seat_no)){
                seat_no = available_seats.get(random.nextInt(available_seats.size()));
            }
            available_seats.remove(available_seats.indexOf(seat_no));
            arrangement.put(ticket_no, seat_no);
            if(display){
                char matched = ticket_no == seat_no ? 'O' : 'X'; 
                System.out.printf("Round %2d, %3d  --> %3d %c %s\n", 
                i+1, ticket_no, seat_no, matched , listToString(available_seats));
            }
        }
        
        var ticket_no = tickets.get(tickets.size() - 1);
        var res = ticket_no == arrangement.get(ticket_no) ;
        if(display){
            System.out.println("Matched: " + res);
        }

        return res ? 1 : 0;
    }

    public static void printMap(HashMap<Integer, Integer> map){
        for(Integer key: map.keySet()){
            System.out.println(key + "@" + map.get(key));
        }
    }
     
    public static String listToString(ArrayList<Integer> list){
        if(list.size() == 0)
            return "[]";
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for(int i = 0; i < list.size() - 1; i++)
            sb.append(list.get(i) + ", ");
        sb.append(list.get(list.size() - 1) + "]");
        return sb.toString();
    }
}
